package javax;

public class Xp_0107 {
    //归并排序||二分排序
    public static void mergeSort(int[] arr){
        if (arr == null || arr.length<2){
            return;
        }

    }
    //归并排序
    public static void sort(int[] arr,int L ,int R){
        if( L==R){
            return;
        }
        int mid = L + (R-L)/2;//L + ((R +　Ｌ)　>>　１)
        sort(arr,L,mid);
        sort(arr,mid+1,R);
        merge(arr,L,mid,R);
    }
    //合并外排
    public static void merge(int[] arr,int L ,int m,int R){
        //help 长度为L到R
        int[] help = new int[R-L+1];
        //辅助数组起点
        int i =0 ;
        //p两边开始的位置
        int p1 = i ;
        int p2 = m+1 ;
        //在对应范围内，都还没越界
        while (p1 <= m && p2 <R){
            help[i++] = arr[p1] <arr[p2] ? arr[p1++] :arr[p2++];
        }
        //两个必有且只有一个越界
        while (p1 <= m){
            help[i++] = arr[p1++];
        }
        while (p2 < R){
            help[i++] = arr[p2++];
        }
        //拷贝回原数组
        for (i=0;i<help.length;i++){
            arr[L+i] = help[i];
        }

    }
}
